#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[100001];
struct node {
	int g[5];
	int r[16];
} t[800001];
int r[100001][7];
void updata(int i) {
	for(int j=1; j<(1<<k); j++)
		t[i].r[j]=t[i*2].r[j]+t[i*2+1].r[j];
	for(int j=1; j<=k; j++) 
		if(t[i].g[j]!=0) 
			for(int sr=(1<<k)-1; sr>=0; sr--) 
				t[i].r[sr|(1<<(j-1))]=t[i].r[sr];
}
void build(int i,int l,int r) {
	if(l==r) {
		t[i].r[0]=1;
		return;
	}
	int mid=(l+r)/2;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
	updata(1);
	t[i].r[0]=t[i*2].r[0]+t[i*2+1].r[0]; 
}
void add(int i,int l,int r,int x,int y,int cd,int z) {
	if(y<x)
		return;
	if(x<=l&&r<=y) {
		t[i].g[cd]+=z;
		updata(i);
		return;
	}
	int mid=(l+r)/2;
	if(y>mid)
		add(i*2+1,mid+1,r,x,y,cd,z);
	if(x<=mid)
		add(i*2,l,mid,x,y,cd,z);
	updata(i);
}
int main() {
	freopen("reporter.in","r",stdin);
	freopen("reporter.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>k;
	for(int i=1; i<=n; i++)
		cin>>a[i];
	build(1,1,n);
	long long ans=0;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=k; j++)
			if(r[a[i]][j])
				add(1,1,n,r[a[i]][j+1]+1,r[a[i]][j],j,-1);
		for(int j=k; j>=1; j--)
			r[a[i]][j+1]=r[a[i]][j];
		r[a[i]][1]=i;
		for(int j=1; j<=k; j++)
			if(r[a[i]][j])
				add(1,1,n,r[a[i]][j+1]+1,r[a[i]][j],j,1);
		ans=ans+1ll*t[1].r[(1<<k)-1];
	}
	cout<<ans;
	return 0;
}
